package com.ma.dp.a02;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Solution651
 * @Author: mayongqiang
 * @DATE 2022/4/25 10:13
 * @Description: 四键键盘
 */
public class Solution651 {
    /*
    假设你有一个特殊的键盘，上面只有四个键，它们分别是：

    1、A 键：在屏幕上打印一个 A。
    2、Ctrl-A 键：选中整个屏幕。
    3、Ctrl-C 键：复制选中的区域到缓冲区。
    4、Ctrl-V 键：将缓冲区的内容输入到光标所在的屏幕上。

    这就和我们平时使用的全选复制粘贴功能完全相同嘛，只不过题目把 Ctrl 的组合键视为了一个键。
    现在要求你只能进行 N 次操作，请你计算屏幕上最多能显示多少个 A？

    N=3 返回3（111）   N=7 返回9 （1112344）
     */
    public static void main(String[] args) {
        //方法一 复杂度N三次
        /* 1、状态  当前还可以按的键数，屏幕上的a的数量，剪贴板里a的数量
           2、选择  四个按键四个选择  a ctrl-a ctrl-c ctrl-v
           3、状态转移  最终要求的结果即为 dp[N][0][0]
                按下a键 dp(n-1,aNum+1,copy)
                按下CTRL-v  dp(n-1,aNum+copy,copy)
                按下ctrl-a,ctrl-c dp(n-2,aNum,copy+aNum)
           4、base case
         */
        System.out.println(maxA(7));
        //方法二、假设最优情况只有以下两种：
        /*
            1、一直按按键1 AAAAA
            2、按x次按键1 AAAAA 后 （ctrl-a + ctrl-c） （ ctrl-v，ctrl-v,......) ， ctrl-a + ctrl-c） （ ctrl-v，ctrl-v,......)  .....
                开头连按几个 A，然后 C-A C-C 组合再接若干 C-V，然后再 C-A C-C 接着若干 C-V，循环下去
                最后一个按键只有可能是A/ctrl-v
            3、定义dp[i] =  表示i次按键后最多的A
            for(int i = 0;i<=N;i++)
                dp[i] = max(按A/按ctrl-v)
              如果选择按键A   子状态转移为 dp[i-1] + 1
              如果选择按键ctrl-v 则需要找到在哪ctrl-a，ctrl-v的
                dp[j-2]*(i-j+1)
          */
        System.out.println(maxA_1(7));
    }

    static int maxA_1(int N) {
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 2; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }
        return dp[N];
    }

    static int maxA(int n) {
        map = new HashMap<>();
        return dp(n, 0, 0);
    }

    static Map<String, Integer> map;

    static int dp(int n, int aNum, int copy) {
        if (n <= 0) return aNum;
        String key = n + "-" + aNum + "-" + copy;
        if (map.containsKey(key)) {
            map.get(key);
        }

        int res = max(dp(n - 1, aNum + 1, copy),
                dp(n - 1, aNum + copy, copy),
                dp(n - 2, aNum, copy + aNum));
        map.put(key, res);
        return res;
    }

    static int max(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
}
